class Solution:
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        mem = [float('inf')]*(amount+1)
        mem[0] = 0
        for coin in coins:
            for j in range(coin, amount+1):
                mem[j] = min(mem[j], mem[j - coin] + 1)# 对于每一个比coin大的值，存在两种可能，一种不适用coin即原本大小，另一种使用coin

        return -1 if mem[-1] > amount else mem[-1]

